Binary Tree Zigzag Traversal
Easy
Question
Given the root of a binary tree, return a list that includes sublists of nodes from each level. The nodes within each sublist should alternate in order between left to right and right to left.
Input: root = [1, 2, 3, 4, None, 6, 7]
Output: [[1], [3, 2], [4, 6, 7]]
The first level lists nodes from left to right: 1. The next level lists nodes from right to left: 3, 2. The next level lists nodes from left to right again: 4, 6, 7.
Input: root = [1, 2, 3, 4, 5, 6, None, 8, 9, None, None, 12]
Output: [[1], [3, 2], [4, 5, 6], [12, 9, 8]]
Input: root = [1, None, 3, None, None, None, 7]
Output: [[1], [3], [7]]
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
What is the zigzag traversal output given the root of this tree? root = [5, 7, 3, 9, 7, None, 2]
[[5], [7, 3], [9, 7, 2]]
[[5], [7, 3], [2, 7, 9]]
[[5], [7, 3], [9, 7, None, 2]]
[[5], [3, 7], [9, 7, 2]]
Take a moment to understand the problem and think of your approach before you start coding.
